package com.demo.test;

import com.alibaba.fastjson2.JSON;
import com.alibaba.fastjson2.TypeReference;

import javax.annotation.PostConstruct;
import java.io.File;
import java.math.BigDecimal;
import java.nio.file.Files;
import java.nio.file.Path;
import java.text.DecimalFormat;
import java.text.NumberFormat;
import java.text.ParseException;
import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;
import java.util.function.Function;
import java.util.regex.Pattern;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class Main {
    public static void main1(String[] args) throws Exception {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        List<Integer> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(scanner.nextInt());
        }
        list.stream().mapToInt(Integer::intValue).distinct().sorted().forEach(System.out::println);
        while (scanner.hasNextLine()) {

        }
    }

    public static void main2(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        char[] charArray = s.toCharArray();
        HashSet<Character> set = new HashSet<>();
        for (char c : charArray) {
            set.add(c);
        }

        System.out.println(set.size());

    }

    public static void main3(String[] args) {

        int[] local = new int[2];
        local[0] = 0;
        local[1] = 0;
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String[] split = s.split(";");
        for (String point : split) {
            if (point.matches("^[ASDW]\\d{1,2}$")) {
                char c = point.charAt(0);
                String substring = point.substring(1);
                int i = Integer.parseInt(substring);
                if (c == 'A') {
                    local[0] = local[0] - i;
                } else if (c == 'S') {
                    local[1] = local[1] - i;
                } else if (c == 'W') {
                    local[1] = local[1] + i;
                } else if (c == 'D') {
                    local[0] = local[0] + i;
                }
            }
        }
        System.out.println(local[0] + "," + local[1]);

    }

    public static void main4(String[] arg) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str = sc.next();
            if (str.length() <= 8) {
                System.out.println("NG");
                continue;
            }
            if (getMatch(str)) {
                System.out.println("NG");
                continue;
            }
            if (getString(str, 0, 3)) {
                System.out.println("NG");
                continue;
            }
            System.out.println("OK");
        }
    }

    // 校验是否有重复子串
    private static boolean getString(String str, int l, int r) {
        if (r >= str.length()) {
            return false;
        }
        if (str.substring(r).contains(str.substring(l, r))) {
            return true;
        } else {
            return getString(str, l + 1, r + 1);
        }
    }

    // 检查是否满足正则
    private static boolean getMatch(String str) {
        int count = 0;
        Pattern p1 = Pattern.compile("[A-Z]");
        if (p1.matcher(str).find()) {
            count++;
        }
        Pattern p2 = Pattern.compile("[a-z]");
        if (p2.matcher(str).find()) {
            count++;
        }
        Pattern p3 = Pattern.compile("[0-9]");
        if (p3.matcher(str).find()) {
            count++;
        }
        Pattern p4 = Pattern.compile("[^a-zA-Z0-9]");
        if (p4.matcher(str).find()) {
            count++;
        }
        if (count >= 3) {
            return false;
        } else {
            return true;
        }
    }

    public static void main5(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        char[] array = s.toCharArray();
        HashMap<Character, Integer> countMap = new HashMap<>();
        for (char c : array) {
            countMap.put(c, countMap.getOrDefault(c, 0) + 1);
        }
        Integer min = Collections.min(countMap.values());
        for (Character c : countMap.keySet()) {
            if (countMap.get(c).equals(min)) {
                s.replaceAll(String.valueOf(c), "");
            }
        }
    }

    public static void main6(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        // ip
        if (s.contains(".")) {
            String[] nums = s.split("\\.");
            for (String num : nums) {
                System.out.println(Integer.toBinaryString(12));
            }
        }
    }

    public static void main7(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
            sc.nextLine();
        }
        int count = 0;
        String str = sc.nextLine();
        char[] chars = str.toCharArray();
        Stack<Integer> s = new Stack<>();
        for (int j = 0; j < chars.length; j++) {
            if (chars[j] == '(') {
                continue;
            } else if (chars[j] == ')') {
                int x = s.pop();
                int y = s.pop();
                int z = s.pop();
                int m = s.pop();
                count += x * y * m;
                s.push(m);
                s.push(x);
            } else {
                s.push(arr[chars[j] - 65][0]);
                s.push(arr[chars[j] - 65][1]);
            }
        }
        System.out.println(count);

    }

    public static void main8(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int flag = sc.nextInt();
        List<Student> students = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            Student student = new Student(sc.next(), sc.nextInt());
            students.add(student);
        }
        if (flag == 1) {
            students.sort(Comparator.comparing(Student::getScore));
        }

        if (flag == 0) {
            students.sort(Comparator.comparing(Student::getScore).reversed());
        }
        students.forEach(System.out::println);

    }

    static class Student {
        private String name;
        private int score;

        public Student() {
        }

        public Student(String name, int score) {
            this.name = name;
            this.score = score;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public int getScore() {
            return score;
        }

        public void setScore(int score) {
            this.score = score;
        }

        @Override
        public String toString() {
            return name + " " + score;
        }
    }

    public static void main9(String[] args) {
        Scanner in = new Scanner(System.in);
        String s1 = in.nextLine();
        String s2 = in.nextLine();
        String shortLen;
        String longLen;
        if (s1.length() > s2.length()) {
            shortLen = s2;
            longLen = s1;
        } else {
            shortLen = s1;
            longLen = s2;
        }
        String maxStr="";

        for (int n = shortLen.length(); n > 0; n--) {
            for (int i = 0; i + n <= shortLen.length(); i++) {

                String substring = shortLen.substring(i, n);
                if (longLen.contains(substring)) {
                    maxStr = substring;
                }
            }
        }
        System.out.println(maxStr);
    }

    public static void main10(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        LinkedList<Integer> list = new LinkedList<>();
        list.add(sc.nextInt());
        for (int i = 0; i < n - 1; i++) {
            int to = sc.nextInt();
            int from = sc.nextInt();
            list.add(list.indexOf(from)+1,to);
        }
        list.remove((Object)sc.nextInt());
//        while (!list.isEmpty()){
//            System.out.print(list.pollFirst()+" ");
//        }
        for (Integer i : list) {
            System.out.print(i+" ");
        }

    }

    public static void main11(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println(jump(sc.nextInt()));
    }
    public static int jump(int n){
        if (n<=1){
            return 1;
        }
        return jump(n-1)+jump(n-2);
    }

    public static void main12(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String t = sc.nextLine();
        System.out.println(kmp(s, t));


    }

    public static int kmp(String s,String t){
        int m = s.length();
        int n = t.length();
        if (n <m|| t.isEmpty()){
            return 0;
        }
        int cnt=0;
        for (int i = 0, j = 0; i < n; i++) {
            while (s.charAt(j)!=t.charAt(i)){
                i=i-j+1;
                j=0;
            }

            if (s.charAt(j)==t.charAt(i)){
                j++;
            }
            if (j==m){
                cnt++;
                j=0;
                i=i-m+2;
            }

        }
        return cnt;
    }

    public int[] getNext(String S){
        int m = S.length();
        int[] next=new int[m];
        for (int i = 1,j=0; i < m; i++) {
            while (S.charAt(i)!=S.charAt(j)){
                j=next[j-1];
            }
            //前缀索引后移
            if(S.charAt(i)==S.charAt(j)) {
                j++;
            }
            //确定应该回退到的下一个索引
            next[i]=j;
        }
        return next;
    }

    public static void main13(String[] args) {



    }
    public int countPrimes(int n) {
      int count = 0;
      for (int i = 2; i < n; i++) {
        if (isPrime(i)){
            count++;
        }
      }
      return count;

    }
    public boolean isPrime(int num) {

        int max= (int) Math.sqrt(num);
        for (int i = 2; i <= max; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }


    public static void main14(String[] args) {
        Integer[] integers = {0,1,2};
        List<Integer> list = Arrays.asList(integers);
        list.set(0,6);
        integers[1]=8;
        System.out.println(Arrays.toString(integers));
        System.out.println(list);
        new ReentrantLock().isHeldByCurrentThread();
        ExecutorService executorService = Executors.newFixedThreadPool(10);


    }



    public static void main15(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(87);
        list.add(87);
        list.add(66);
        list.add(89);
        list.add(99);
        list.add(100);
        list.add(87);
        list.add(88);
        list.add(90);
        list.add(95);
        list.add(78);
        list.add(67);
        list.add(89);
        list.add(90);
        list.add(86);
        list.add(77);
        list.add(91);
        list.add(96);
        list.add(93);
        list.add(100);
        list.add(89);
        list.add(98);
        list.add(92);
        list.add(65);
        list.add(92);
        list.add(97);
        list.add(86);
        list.add(82);
        list.add(96);
        list.add(96);
        list.add(89);
        list.add(88);
        list.add(90);
        list.add(68);
        list.add(93);
        list.add(84);
        list.add(92);
        list.add(86);
        list.add(94);
        list.add(94);
        list.add(90);
        list.add(97);
        list.add(98);
        list.add(84);
        list.add(84);
        list.add(92);
        list.add(95);
        list.add(94);
        list.add(98);
        list.add(93);
        list.add(95);
        list.add(92);
        list.add(97);
        list.add(79);
        list.add(90);
        list.add(94);
        list.add(97);
        list.add(90);
        list.add(85);
        IntSummaryStatistics statistics = list.stream().mapToInt(Integer::intValue).summaryStatistics();
        System.out.println(statistics);
        list.stream().mapToInt(Integer::intValue).sorted().skip(29).findFirst().ifPresent(System.out::println);
        Map<Integer, Long> scoreRanges = list.stream()
                .collect(Collectors.groupingBy(score -> score / 5*5, Collectors.counting()));
        scoreRanges.entrySet().stream()
                .sorted(Map.Entry.comparingByKey(Comparator.reverseOrder()))
                .forEach(a->System.out.print(a+" "));

    }

    public static void main16(String[] args) throws ParseException {
        BigDecimal bigDecimal = new BigDecimal("1222.22");
        DecimalFormat decimalFormat = new DecimalFormat("#,##0.00");
        String format = decimalFormat.format(bigDecimal);
        NumberFormat percentFormat = NumberFormat.getPercentInstance();
        percentFormat.setMinimumFractionDigits(2);
        String percentage = percentFormat.format(new BigDecimal("0.3"));
        Number parse = percentFormat.parse(percentage);
        System.out.println(percentage);
        System.out.println(parse);
    }

    public static void main(String[] args) {
        PriorityQueue<Integer> silverPieces = new PriorityQueue<>(Collections.reverseOrder());
        silverPieces.poll();
        HashMap<String, Integer> map = new HashMap<>();
//        map.putIfAbsent()
//Arrays.binarySearch()
        int i = Integer.parseInt("10", 2);
        System.out.println(i);
        String str = "/Hello/World";
        String result = str.replace("/", "");
        System.out.println(result);
// 输出：HelloWorld，所有的“/”都被去掉了。
        boolean[] booleans = new boolean[10];
        System.out.println(booleans[0]);
        LinkedHashMap<String, Integer> lmap = new LinkedHashMap<>();
        lmap.put("b",2);
        lmap.put("a",1);
        lmap.put("c",3);
        lmap.forEach((k,v)-> System.out.println(k+":"+v));
        new PriorityQueue<Integer>(Collections.reverseOrder());
        byte[] encode = Base64.getEncoder().encode(new byte[]{1, 2, 3, 4, 5, 6, 7, 8, 9});
        System.out.println(encode);
        Scanner sc = new Scanner(System.in);
        List<Object> objects = Collections.synchronizedList(new ArrayList<>());
    }




}